package leetcode.stack;

import java.util.LinkedList;

public class getNum {
    public static int getNum(int[] arr,int num){
        if (arr ==null || arr.length == 0 || num<0){
            return 0;
        }
        LinkedList<Integer> qmin = new LinkedList<>();
        LinkedList<Integer> qmax = new LinkedList<>();
        int i =0;
        int j =0;
        int res = 0;
        while (i<arr.length){
            while (j<arr.length){
                if (qmin.isEmpty() || qmin.peekFirst() !=j){
                    while (!qmin.isEmpty() && arr[qmin.peekLast()]>=arr[j]){
                        qmin.pollLast();
                    }
                    qmin.addLast(j);
                    while (!qmax.isEmpty() && arr[qmax.peekLast()] <=arr[j]){
                        qmax.pollLast();
                    }
                    qmax.addLast(j);
                }
                if(arr[qmax.getFirst()]-arr[qmin.getFirst()]>num){
                    break;
                }
                j++;
            }
            res+=j-i;
            if (qmin.peekFirst()==i){
                qmin.pollFirst();
            }
            if (qmax.peekFirst()==i){
                qmax.pollFirst();
            }
            i++;
        }
        return res;
    }
}
